home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / FSET.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  14KB  |  488 lines
  1. /*
  2.  * fset.c
  3.  *
  4.  * Compute FIRST and FOLLOW sets.
  5.  *
  6.  * SOFTWARE RIGHTS
  7.  *
  8.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  9.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  10.  * company may do whatever they wish with source code distributed with
  11.  * PCCTS or the code generated by PCCTS, including the incorporation of
  12.  * PCCTS, or its output, into commerical software.
  13.  * 
  14.  * We encourage users to develop software with PCCTS.  However, we do ask
  15.  * that credit is given to us for developing PCCTS.  By "credit",
  16.  * we mean that if you incorporate our source code into one of your
  17.  * programs (commercial product, research project, or otherwise) that you
  18.  * acknowledge this fact somewhere in the documentation, research report,
  19.  * etc...  If you like PCCTS and have developed a nice tool with the
  20.  * output, please mention that you developed it using PCCTS.  In
  21.  * addition, we ask that this header remain intact in our source code.
  22.  * As long as these guidelines are kept, we expect to continue enhancing
  23.  * this system and expect to make other tools available as they are
  24.  * completed.
  25.  *
  26.  * ANTLR 1.06
  27.  * Terence Parr
  28.  * Purdue University
  29.  * 1989-1992
  30.  */
  31. #include <stdio.h>
  32. #include "set.h"
  33. #include "syn.h"
  34. #include "hash.h"
  35. #include "generic.h"
  36. #include "dlgdef.h"
  37.  
  38. /*
  39.  * What tokens are k tokens away from junction q?
  40.  *
  41.  * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
  42.  * node.
  43.  * We lock the junction according to k--the lookahead.  If we have been at this
  44.  * junction before looking for the same, k, number of lookahead tokens, we will
  45.  * do it again and again...until we blow up the stack.  Locks are only used on aLoopBlk,
  46.  * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
  47.  * FIRST and FOLLOW calcs.
  48.  *
  49.  * If p->jtype == EndRule we are going to attempt a FOLLOW.  (FOLLOWs are really defined
  50.  * in terms of FIRST's, however).  To proceed with the FOLLOW, p->halt cannot be
  51.  * set.  p->halt is set to indicate that a reference to the current rule is in progress
  52.  * and the FOLLOW is not desirable.
  53.  *
  54.  * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
  55.  * junction yields an empty set, replace the empty set with EOF.  No FOLLOW means that
  56.  * only EOF can follow the current rule.  This normally occurs only on the start symbol
  57.  * since all other rules are referenced by another rule somewhere.
  58.  *
  59.  * Normally, both p1 and p2 are followed.  However, checking p2 on a RuleBlk node is
  60.  * the same as checking the next rule which is clearly incorrect.
  61.  *
  62.  * Cycles in the FOLLOW sense are possible.  e.g. Fo(c) requires Fo(b) which requires
  63.  * Fo(c).  Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c).  Let's say
  64.  * Fo(c) is attempted first.  It finds all of the FOLLOW symbols and then attempts
  65.  * to do Fo(b) which finds of its FOLLOW symbols.  So, we have:
  66.  *
  67.  *                  Fo(c)
  68.  *                 /     \
  69.  *              a set    Fo(b)
  70.  *                      /     \
  71.  *                   a set    Fo(c) .....Hmmmm..... Infinite recursion!
  72.  *
  73.  * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
  74.  * correctly Fo(c) union Fo(b).  We wish to pick up where we left off, so the fact
  75.  * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
  76.  * laying around.  SOOOOoooo, we track FOLLOW cycles.  All FOLLOW computations are
  77.  * cached in a hash table.  After the sequence of FOLLOWs finish, we reconcile all
  78.  * cycles --> correct all Fo(rule) sets in the cache.
  79.  *
  80.  * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
  81.  *
  82.  * Also, FIRST sets are cached in the hash table.  Keys are (rulename,Fi/Fo,k).
  83.  * Only FIRST sets, for which the FOLLOW is not included, are stored.
  84.  */
  85. set
  86. rJunc(p,k,rk)
  87. Junction *p;
  88. int k;
  89. set *rk;
  90. {
  91.     set a, b;
  92.     require(p!=NULL,                "rJunc: NULL node");
  93.     require(p->ntype==nJunction,    "rJunc: not junction");
  94.  
  95.     /*if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);
  96.     else fprintf(stderr, "rJunc: %s in rule %s\n",
  97.             decodeJType[p->jtype], ((Junction *)p)->rname);
  98.     */
  99.     /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
  100.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  101.          p->jtype==aPlusBlk || p->jtype==EndRule ) 
  102.     {
  103.         require(p->lock!=NULL, "rJunc: lock array is NULL");
  104.         if ( p->lock[k] )
  105.         {
  106.             if ( p->jtype == EndRule )    /* FOLLOW cycle? */
  107.             {
  108.                 /*fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);*/
  109.                 RegisterCycle(p->rname, k);
  110.             }
  111.             return empty;
  112.         }
  113.         if ( p->jtype == RuleBlk && p->end->halt )    /* check for FIRST cache */
  114.         {
  115.             CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
  116.             if ( q != NULL )
  117.             {
  118.                 set_orin(rk, q->rk);
  119.                 return set_dup( q->fset );
  120.             }
  121.         }
  122.         if ( p->jtype == EndRule )        /* FOLLOW set cached already? */
  123.         {
  124.             CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
  125.             if ( q != NULL )
  126.             {
  127.                 /*fprintf(stderr, "<->FOLLOW(%s,%d):", p->rname,k);
  128.                 s_fprT(stderr, q->fset);
  129.                 if ( q->incomplete ) fprintf(stderr, " (incomplete)");
  130.                 fprintf(stderr, "\n");
  131.                 */
  132.                 if ( !q->incomplete )
  133.                 {
  134.                     return set_dup( q->fset );
  135.                 }
  136.             }
  137.         }
  138.         p->lock[k] = TRUE;    /* This rule is busy */
  139.     }
  140.  
  141.     a = b = empty;
  142.  
  143.     if ( p->jtype == EndRule )
  144.     {
  145.         if ( p->halt )                                /* don't want FOLLOW here? */
  146.         {
  147.             p->lock[k] = FALSE;
  148.             set_orel(k, rk);                        /* indicate this k value needed */
  149.             return empty;
  150.         }
  151.         FoPush(p->rname, k);                        /* Attempting FOLLOW */
  152.         if ( p->p1 == NULL ) set_orel(EofToken, &a);/* if no FOLLOW assume EOF */
  153.         /*fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);*/
  154.     }
  155.  
  156.     if ( p->p1 != NULL ) REACH(p->p1, k, rk, a);
  157.     
  158.     /* C a c h e  R e s u l t s */
  159.     if ( p->jtype == RuleBlk && p->end->halt )        /* can save FIRST set? */
  160.     {
  161.         CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );
  162.         /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
  163.         hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);
  164.         q->fset = set_dup( a );
  165.         q->rk = set_dup( *rk );
  166.     }
  167.  
  168.     if ( p->jtype == EndRule )                        /* just completed FOLLOW? */
  169.     {
  170.         /* Cache Follow set */
  171.         CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
  172.         if ( q==NULL )
  173.         {
  174.             q = newCacheEntry( Fkey(p->rname,'o',k) );
  175.             hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
  176.         }
  177.         /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
  178.         set_orin(&(q->fset), a);
  179.         FoPop( k );
  180.         if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
  181.         /*
  182.         fprintf(stderr, "<--FOLLOW(%s,%d):", p->rname, k);
  183.         s_fprT(stderr, q->fset);
  184.         if ( q->incomplete ) fprintf(stderr, " (incomplete)");
  185.         fprintf(stderr, "\n");
  186.         */
  187.     }
  188.     
  189.     if ( p->jtype != RuleBlk && p->p2 != NULL ) REACH(p->p2, k, rk, b);
  190.     if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
  191.          p->jtype==aPlusBlk || p->jtype==EndRule ) 
  192.         p->lock[k] = FALSE;                            /* unlock node */
  193.  
  194.     set_orin(&a, b);
  195.     set_free(b);
  196.     return a;
  197. }
  198.  
  199. set
  200. rRuleRef(p,k,rk_out)
  201. RuleRefNode *p;
  202. int k;
  203. set *rk_out;
  204. {
  205.     set rk;
  206.     Junction *r;
  207.     int k2;
  208.     set a, rk2, b;
  209.     int save_halt;
  210.     RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
  211.     require(p!=NULL,            "rRuleRef: NULL node");
  212.     require(p->ntype==nRuleRef,    "rRuleRef: not rule ref");
  213.  
  214.     /*fprintf(stderr, "rRuleRef: %s\n", p->text);*/
  215.     if ( q == NULL )
  216.     {
  217.         warnNoFL( eMsg1("rule %s not defined",p->text) );
  218.         REACH(p->next, k, rk_out, a);
  219.         return a;
  220.     }
  221.     rk2 = empty;
  222.     r = RulePtr[q->rulenum];
  223.     if ( r->lock[k] )
  224.     {
  225.         warnNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
  226.                         r->rname, p->rname) );
  227.         return empty;
  228.     }
  229.     save_halt = r->end->halt;
  230.     r->end->halt = TRUE;        /* don't let reach fall off end of rule here */
  231.     rk = empty;
  232.     REACH(r, k, &rk, a);
  233.     r->end->halt = save_halt;
  234.     while ( !set_nil(rk) ) {
  235.         k2 = set_int(rk);
  236.         set_rm(k2, rk);
  237.         REACH(p->next, k2, &rk2, b);
  238.         set_orin(&a, b);
  239.         set_free(b);
  240.     }
  241.     set_orin(rk_out, rk2);        /* remember what we couldn't do */
  242.     set_free(rk2);
  243.     return a;
  244. }
  245.  
  246. set
  247. rToken(p,k,rk)
  248. TokNode *p;
  249. int k;
  250. set *rk;
  251. {
  252.     set a;
  253.     require(p!=NULL,            "rToken: NULL node");
  254.     require(p->ntype==nToken,    "rToken: not token node");
  255.  
  256.     /*fprintf(stderr, "rToken: %s\n", (TokenStr[p->token]!=NULL)?TokenStr[p->token]:
  257.                                     ExprStr[p->token]);*/
  258.     if ( k-1 == 0 ) return set_of( p->token );
  259.     REACH(p->next, k-1, rk, a);
  260.     
  261.     return a;
  262. }
  263.  
  264. set
  265. rAction(p,k,rk)
  266. ActionNode *p;
  267. int k;
  268. set *rk;
  269. {
  270.     set a;
  271.     require(p!=NULL,            "rJunc: NULL node");
  272.     require(p->ntype==nAction,    "rJunc: not action");
  273.     
  274.     REACH(p->next, k, rk, a);    /* ignore actions */
  275.     return a;
  276. }
  277.  
  278.                 /* A m b i g u i t y  R e s o l u t i o n */
  279.  
  280.  
  281. static void
  282. dumpAmbigMsg(fset)
  283. set *fset;
  284. {
  285.     int i;
  286.  
  287.     fprintf(stderr, " ");
  288.     for (i=1; i<=LL_k; i++)
  289.     {
  290.         if ( i>1 ) fprintf(stderr, ", ");
  291.         if ( set_deg(fset[i]) > 3 && elevel == 1 )
  292.         {
  293.             int e,m;
  294.             fprintf(stderr, "{");
  295.             for (m=1; m<=3; m++)
  296.             {
  297.                 e=set_int(fset[i]);
  298.                 fprintf(stderr, " %s", TerminalString(e));
  299.                 set_rm(e, fset[i]);
  300.             }
  301.             fprintf(stderr, " ... }");
  302.         }
  303.         else s_fprT(stderr, fset[i]);
  304.     }
  305.     fprintf(stderr, "\n");
  306.     for (i=1; i<=LL_k; i++) set_free( fset[i] );
  307.     free(fset);
  308. }
  309.  
  310. void
  311. HandleAmbiguity(alt1,alt2,jtype)
  312. Junction *alt1, *alt2;
  313. int jtype;
  314. {
  315.     unsigned **ftbl;
  316.     set *fset, b;
  317.     int i, numAmbig, n, n2;
  318.     Tree *ambig, *t, *u;
  319.     char *sub = "";
  320.  
  321.     fset = (set *) calloc(LL_k+1, sizeof(set));
  322.     require(fset!=NULL, "cannot allocate fset");
  323.     ftbl = (unsigned **) calloc(LL_k+1, sizeof(unsigned *));
  324.     require(ftbl!=NULL, "cannot allocate ftbl");
  325.     /* create constraint table and count number of possible ambiguities */
  326.     for (n=1,i=1; i<=LL_k; i++)
  327.     {
  328.         b = set_and(alt1->fset[i], alt2->fset[i]);
  329.         n *= set_deg(b);
  330.         fset[i] = set_dup(b);
  331.         ftbl[i] = set_pdq(b);
  332.         set_free(b);
  333.     }
  334.  
  335.     switch ( jtype )
  336.     {
  337.         case aSubBlk: sub = "of (..) "; break;
  338.         case aOptBlk: sub = "of {..} "; break;
  339.         case aLoopBegin: sub = "of (..)* "; break;
  340.         case aLoopBlk: sub = "of (..)* "; break;
  341.         case aPlusBlk: sub = "of (..)+ "; break;
  342.         case RuleBlk: sub = "of rule "; break;
  343.         default : sub = ""; break;
  344.     }
  345.  
  346.     /* if all sets have degree 1 for k<LL_k, then ambig upon all permutation */
  347.     n2 = 0;
  348.     for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);
  349.     if ( n2==2*(LL_k-1) )
  350.     {
  351.         /* C O D E  F O R  P R E D I C A T E S  (ambiguous--check for predicates) */
  352.         if ( ParseWithPredicates )
  353.         {
  354.             alt1->predicate = find_predicates((Node *)alt1->p1);
  355.             alt2->predicate = find_predicates((Node *)alt2->p1);
  356.         }
  357.  
  358.         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  359.         if ( jtype == aLoopBegin )
  360.             fprintf(stderr, " warning: optional path and alt(s) of (..)* ambiguous upon");
  361.         else
  362.             fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  363.                         alt1->altnum, alt2->altnum, sub);
  364.         dumpAmbigMsg(fset);
  365.         for (i=1; i<=LL_k; i++) free( ftbl[i] );
  366.         free(ftbl);
  367.         return;
  368.     }
  369.  
  370.     /* in case tree construction runs out of memory, set info to make good err msg */
  371.     CurAmbigAlt1 = alt1->altnum;
  372.     CurAmbigAlt2 = alt2->altnum;
  373.     CurAmbigbtype = sub;
  374.     CurAmbigfile = alt1->file;
  375.     CurAmbigline = alt1->line;
  376.     
  377.     ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);
  378.     for (i=1; i<=LL_k; i++) free( ftbl[i] );
  379.     free(ftbl);
  380.  
  381.     /* are all things in intersection really ambigs? */
  382.     if ( numAmbig < n )
  383.     {
  384.         Tree *v;
  385.  
  386.         /* remove ambig permutation from 2nd alternative to resolve ambig */
  387.         if ( ambig!=NULL )
  388.         {
  389.             for (v=ambig->down; v!=NULL; v=v->right)
  390.             {
  391.                 u = trm_perm(u, v);
  392.             }
  393.             /*fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
  394.         }
  395.         Tfree( t );
  396.         alt1->ftree = tappend(alt1->ftree, u);
  397.         alt1->ftree = tleft_factor(alt1->ftree);
  398.     }
  399.  
  400.     if ( ambig==NULL )
  401.     {
  402.         for (i=1; i<=LL_k; i++) set_free( fset[i] );
  403.         free(fset);
  404.         return;
  405.     }
  406.  
  407.     /* C O D E  F O R  P R E D I C A T E S  (ambiguous k>1 --check for predicates) */
  408.     if ( ParseWithPredicates )
  409.     {
  410.         alt1->predicate = find_predicates((Node *)alt1->p1);
  411.         alt2->predicate = find_predicates((Node *)alt2->p1);
  412.     }
  413.  
  414.     ambig = tleft_factor(ambig);
  415.  
  416.     fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
  417.     if ( jtype == aLoopBegin )
  418.         fprintf(stderr, " warning: optional path and alt(s) of (..)* ambiguous upon");
  419.     else
  420.         fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
  421.                     alt1->altnum, alt2->altnum, sub);
  422.     if ( elevel == 3 )
  423.     {
  424.         preorder(ambig->down);
  425.         fprintf(stderr, "\n");
  426.         Tfree(ambig);
  427.         return;
  428.     }
  429.     Tfree(ambig);
  430.     dumpAmbigMsg(fset);
  431. }
  432.  
  433. set
  434. First(j,k,jtype,max_k)
  435. Junction *j;
  436. int k, jtype;
  437. int *max_k;
  438. {
  439.     Junction *alt1, *alt2;
  440.     set a, rk, fCurBlk;
  441.     int savek;
  442.     require(j->ntype==nJunction, "First: non junction passed");
  443.  
  444.     /* C o m p u t e  F I R S T  s e t  w i t h  k  l o o k a h e a d */
  445.     fCurBlk = rk = empty;
  446.     for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
  447.     {
  448.         REACH(alt1->p1, k, &rk, alt1->fset[k]);
  449.         require(set_nil(rk), "rk != nil");
  450.         set_orin(&fCurBlk, alt1->fset[k]);
  451.     }
  452.  
  453.     /* D e t e c t  A m b i g u i t i e s */
  454.     *max_k = 1;
  455.     for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
  456.     {
  457.         for (alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2)
  458.         {
  459.             savek = k;
  460.             a = set_and(alt1->fset[k], alt2->fset[k]);
  461.             while ( !set_nil(a) )
  462.             {
  463.                 if ( k==LL_k )
  464.                 {
  465.                     *max_k = LL_k;
  466.                     HandleAmbiguity(alt1, alt2, jtype);
  467.                     break;
  468.                 }
  469.                 else
  470.                 {
  471.                     k++;    /* attempt ambig alts again with more lookahead */
  472.                     REACH(alt1->p1, k, &rk, alt1->fset[k]);
  473.                     require(set_nil(rk), "rk != nil");
  474.                     REACH(alt2->p1, k, &rk, alt2->fset[k]);
  475.                     require(set_nil(rk), "rk != nil");
  476.                     set_free(a);
  477.                     a = set_and(alt1->fset[k], alt2->fset[k]);
  478.                     if ( k > *max_k ) *max_k = k;
  479.                 }
  480.             }
  481.             set_free(a);
  482.             k = savek;
  483.         }
  484.     }
  485.     
  486.     return fCurBlk;
  487. }
  488.